Định lý Euler về chu trình và đường đi Euler Đường_đi_Euler
Đồ thị Bảy cây cầu Königsberg có 4 đỉnh bậc lẻ nên không là đồ thị Euler
Đồ thị vô hướng liên thông G = (X, E) có chu trình Euler khi và chỉ khi G không có đỉnh bậc lẻ.
Chứng minh:
Điều kiện cần: Giả sử (G) là đồ thị Euler, tức là tồn tại chu trình Euler (P) trong (G). Khi đó, cứ mỗi lần chu trình (P) đi qua một đỉnh nào đó của (G) thì bậc của đỉnh đó tăng lên 2.
Mặt khác, mỗi cạnh của đồ thị xuất hiện trong (P) đúng 1 lần. Do đó, mỗi đỉnh của đồ thị đều có bậc chẵn.
Phát biểu khác: Một đa đồ thị không có điểm cô lập có chu trình Euler nếu và chỉ nếu đồ thị là liên thông và mỗi đỉnh của nó đều có bậc chẵn.
Đồ thị vô hướng liên thông G = (X, E) có đường đi Euler khi và chỉ khi G có đúng hai đỉnh bậc lẻ. Nếu G có hai đỉnh bậc lẻ thì đường đi Euler có hai đầu đường đi nằm ở hai đỉnh bậc lẻ.
Đồ thị có hướng liên thông G = (X, E) có chu trình Euler, khi đó số đỉnh bậc trong của G sẽ bằng số đỉnh bậc ngoài của G (d+(x) = d-(x),∀xϵ X).
